package 代码题.排列组合题目;

/**
 * 有重复字符的全排列
 */
public class RepeatAllPermutations {

    /**
     * 思路：如果给的字符中出现重复，即{a,b,c,c}这种情况，可以判断当前准备交换的字符，
     * 如果当前准备交换的字符已经在cur前面的字符中出现过了，就跳过，否则就交换。修改后方法如下：
     *
     * @param args
     */
    public static void main(String[] args) {
        char[] array=new char[]{'a','b','c','c'};
        helper(array,0);
    }

    public static void helper(char[] array, int cur){
        if ( cur == array.length - 1 ){
            System.out.println(array);
        }
        else {
            for ( int i = cur ; i < array.length ; i ++ ){
                if (!isExit(array, cur, i)) {
                    swap(array, cur, i);
                    helper(array, cur + 1);  //固定第一个字符，对后面所有字符全排列
                    swap(array, i, cur);
                }
            }
        }
    }

    public static void swap(char[] array,int first,int second){
        char tmp=array[first];
        array[first]=array[second];
        array[second]=tmp;
    }

    private static boolean isExit(char[] array, int cur, int i) {
        for ( int k = cur ; k < i ; k ++ ){
            if ( array[k] == array[i] ) {
                return true;
            }
        }
        return false;
    }
}
